#!/usr/bin/env python

import random

# -------------------- game config --------------------

display = True
human = False

# -------------------- board --------------------

N, M, GAMES = 6, 7, 100
DELTAS_ALL = [(x, y) for x in [-1, 0, 1] for y in [-1, 0, 1] if x or y]
DELTAS = [(x, y) for (x, y) in DELTAS_ALL if x + x + y > 0]

class board:

    def __init__(self):
        self.s = [['.'] * M for i in range(N)]
        self.top = [N] * M

    def __str__(self):
        res = ' '.join(map(str, range(M))) + '\n'
        for s in [' '.join(row) for row in self.s]: res += s + '\n'
        return res

    def read(self):
        for i in range(N):
            l = raw_input()
            self.s[i] = l.split(' ')
        for j in range(M):
            self.top[j] = N
            for i in range(N):
                if self.s[i][j] != '.':
                    self.top[j] = i
                    break

    def pieces(self):
        cnt = 0
        for t in self.top:
            cnt += N - t
        return cnt

    def put(self, y, v):
        self.top[y] -= 1
        self.s[self.top[y]][y] = v

    def unput(self, y):
        self.s[self.top[y]][y] = '.'
        self.top[y] += 1

    def can_put(self, y):
        return self.top[y] > 0

    def can_win_immediately(self, role):
        for y in range(M):
            if self.can_put(y):
                self.put(y, role)
                w = self.winner()
                self.unput(y)
                if w == role: return True
        return False

    @staticmethod
    def h(x):
        return x ** 2 + 10

    def score(self, role):
        res = 0
        s = self.s
        for y in range(M):
            for x in range(N):
                for dx, dy in DELTAS:
                    if board.inside_board(x + 3 * dx, y + 3 * dy):
                        a, b = 0, 0
                        for i in range(4):
                            x1, y1 = x + i * dx, y + i * dy
                            if s[x1][y1] == role: 
                                a += 1
                            elif s[x1][y1] != '.':
                                b += 1
                        if b == 0:
                            res += board.h(a)
                        elif a == 0:
                            res -= board.h(b)
        return res

    @staticmethod
    def inside_board(x, y):
        return 0 <= x < N and 0 <= y < M

    def winner(self):
        s = self.s
        for y in range(M):
            for x in range(self.top[y], N):
                for dx, dy in DELTAS:
                    if board.inside_board(x + 3 * dx, y + 3 * dy):
                        flag = True
                        for i in range(1, 4):
                            flag &= s[x][y] == s[x + i * dx][y + i * dy]
                        if flag: return s[x][y]

    def full(self):
        for y in range(M):
            if self.can_put(y): 
                return False
        return True

    def ended(self):
        return self.winner() or self.full()

# -------------------- random ai --------------------

def random_player(b, role):
    ys = [y for y in range(M) if b.can_put(y)]
    random.shuffle(ys)
    return ys[0]

# -------------------- smart ai --------------------

big = 10000
inf = 1000000000

def smart_dfs(b, role, depth, alpha):
    winner = b.winner()
    if winner:
        return (big, -1) if winner == role else (-big, -1)

    if b.full():
        return 0, -1

    # TODO cache

    ys = [y for y in range(M) if b.can_put(y)]
    random.shuffle(ys)

    if depth <= 0:
        return (b.score(role), ys[0])

    best = (-inf, -1)
    for y in ys:
        b.put(y, role)
        s, y1 = smart_dfs(b, opponent(role), depth - 1, -best[0])
        b.unput(y)

        tt = (-s + sign(s), y)
        if tt[0] > best[0]: best = tt
#     if depth == 6: print tt

        if -alpha >= s: break
    return best

def smart_think(b, role, max_depth):
    score, y = smart_dfs(b, role, max_depth, inf)
# print 'score is', score, 'y is', y
    return y

def make_smart_player(level):
    return lambda b, r: smart_think(b, r, level)

# -------------------- human player --------------------

def reasonable(b, role, y1):
    b.put(y1, role)
    c = b.can_win_immediately(opponent(role))
    b.unput(y1)
    if not c: return True
    for y in range(M):
        if b.can_put(y):
            b.put(y, role)
            c = b.can_win_immediately(opponent(role))
            b.unput(y)
            if not c: return False
    return True

def human_player(b, role):
    if not display or b.pieces() == 0: print b
    while True:
        y = input('input y: ')
        if reasonable(b, role, y) or raw_input('are you sure? (y/n) ') == 'y': break
    return y

# -------------------- player settings --------------------

if human:
    players = [('x', human_player), ('o', make_smart_player(6))]
else:
    players = [('x', make_smart_player(5)), ('o', make_smart_player(6))]

# -------------------- utils --------------------

def opponent(role):
    for r, ai in players:
        if r != role:
            return r
    return None

def sign(x):
    if x > 0:
        return 1
    elif x < 0:
        return -1
    return 0

def list_swap(l):
    t = l[0]
    l[0] = l[1]
    l[1] = t

# -------------------- main --------------------

def main():

    result = { players[0][0]: 0, players[1][0]: 0, 'draw': 0 }
    
    for k in range(GAMES):
        b = board()
        while not b.ended():
            for role, ai in players:
                y = ai(b, role)
                b.put(y, role)
                if display: print b
                if b.ended(): break
        
        w = b.winner()
        result[w or 'draw'] += 1

        list_swap(players)

        for k, v in result.items():
            print '%s:%d' % (k, v),
        print

if __name__ == '__main__': 
    main()
